#ifndef __MAXSUBARRAY__
#define __MAXSUBARRAY__

// CLRS - Page 70.

class algo_maxsubarray{
	int *p;
	int size;
	struct data{
		int maxval;
		int *start;
		int *end;
	};

private:
	
	data getmaxsubarraycross(int* p, int size){
		data d={INT_MIN,NULL,p+size-1};
		int tmp = 0;
		for (int i=size/2-1;i>=0;i--){
			tmp += p[i];
			if (d.maxval<tmp){
				d.maxval = tmp;
				d.start = p+i;
			}
		}
		tmp=d.maxval;
		int i=size/2;
		while(i<size){
			tmp += p[i];
			i++;
			if (d.maxval<tmp){
				d.maxval = tmp;
				d.end = p+i;
			}
		}
		return d;
	}

	data getmaxsubarray(int* p, int size){
		data d={INT_MIN,NULL,NULL};
		if (size==1){
			d.maxval = p[size-1];
			d.start = d.end = p+size-1;
			return d;
		}else{
			data a1 = getmaxsubarray(p,size/2);
			data a2 = getmaxsubarray(p+size/2,size-size/2);//Cannot write as getmaxsubarray(p+size/2,size/2)
			data a3 = getmaxsubarraycross(p,size);
			return maxdata(maxdata(a1,a2),a3);
		}
	}

	data maxdata(const data lhs,const data rhs) const{
		return (lhs.maxval>rhs.maxval)?lhs:rhs;
	}


public:
	algo_maxsubarray(int* _p, int s):p(_p),size(s){}
	void getmaxvalue(int& maxval, int* &p1,int* &p2){
		data d = getmaxsubarray(p,size);
		maxval = d.maxval;
		p1 = d.start;
		p2 = d.end;
	}
};


void test_maxsubarray_oo(){
	int maxval=0;
	int *start=NULL, *end=NULL;//  Be careful!!! not int *start, end;
	{
		int a[] = {12, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, 22};
		algo_maxsubarray am(a,sizeof(a)/sizeof(int));
		am.getmaxvalue(maxval,start,end);
		cout << "Max Value:" << maxval << endl;
		do{
			cout << start[0] << endl;
			start++;
		}while(start <= end);
	}
	{
		int a[] = {-12};
		algo_maxsubarray am(a,sizeof(a)/sizeof(int));
		am.getmaxvalue(maxval,start,end);
		cout << "Max Value:" << maxval << endl;
		do{
			cout << start[0] << endl;
			start++;
		}while(start <= end);
	}
	{
		int a[] = {-12,5};
		algo_maxsubarray am(a,sizeof(a)/sizeof(int));
		am.getmaxvalue(maxval,start,end);
		cout << "Max Value:" << maxval << endl;
		do{
			cout << start[0] << endl;
			start++;
		}while(start <= end);
	}
	getchar();
}

int getmaxsubarraycross(int *p,int size){
	int maxval1 = INT_MIN;
	int tmp = 0;
	for (int i=size/2-1;i>=0;i--){
		tmp += p[i];
		if (maxval1<tmp){
			maxval1 = tmp;
		}
	}
	tmp=0;
	int i=size/2;
	int maxval2=INT_MIN;
	while(i<size){
		tmp += p[i];
		i++;
		if (maxval2<tmp){
			maxval2 = tmp;
		}
	}
	return maxval1+maxval2;
}

int getmaxsubarray(int *p, int size){
	if (size==1){
		return p[size-1];
	}else{
		int a1 = getmaxsubarray(p,size/2);
		int a2 = getmaxsubarray(p+size/2,size-size/2);
		int a3 = getmaxsubarraycross(p,size);
		return max(max(a1,a2),a3);
	}
}

void test_maxsubarray(){
	int a[] = {12, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
	int m=getmaxsubarray(a,sizeof(a)/sizeof(int));
	cout << m << endl;
}

#endif

